perm filename PUZZ.DDG[ESS,JMC]1 blob sn#182424 filedate 1975-10-19 generic text, type T, neo UTF8
00100	Here is the solution to your puzzle of last night:  Let  p(n) be the
00200	position  mod n  of the person who should be in the  n th place and
00300	let  r(n)  be the amount the table must be rotated to bring him to
00400	his correct place - all assuming  N  people numbered  0,1,...,N-1.
00500	Unless the  N  r(n)'s  are precisely the  N  numbers  0,1,...,N-1,
00600	rotating by the missing number will bring everyone to the wrong place.
00700	If they are, then adding up the  N  congruences  p(n) + r(n) = n mod N,
00800	each expressing that rotating the table by  r(n)  will bring the
00900	person who should be at position  n  from position  p(n) to that position,
01000	gives the congruence  (N↑2-N)/2 + (N↑2-N)/2 ≡ (N↑2-N)/2 mod N.
01100	since the first summands, the second summands and the right hand sides
01200	each form the set {0,1,...,N-1}.  Setting  N = 2K gives a left side
01300	congruent to zero and a right side congruent to K.  This shows that
01400	the  r(n)'s  cannot be all different, and so there must be a rotation
01500	←utting everyone in the wrong place.
01600	
01700		If  N  is odd, then setting  p(n) = -n, i.e. reversing the
01800	order of the guests produces a configuration in which any rotation
01900	puts some guest in the right position, because then  r(n) = 2n, and
02000	since  2  and  N  are relatively prime, the  2n  are again a complete
02100	set of residues.  The only remaining question is what other suitable
02200	configurations exist in the odd case.